package strain.domain.interval_set;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * This is a set based on intervals
 * @author bhorner
 *
 */
public class IntervalSet implements Iterable<Interval> {
	
	public static IntervalSet NULL = new IntervalSet();
	public static IntervalSet UNIVERSE = new IntervalSet(Interval.UNIVERSE);
	
	public static Comparator<Interval> LOWER_UPPER = new Comparator<Interval>(){
		
		public int compare(Interval i1, Interval i2){
			// put NULL first...
			int result = 0;
			if (i1.isNull()){
				if (i2.isNull()){
					result = 0;   // both are null
				} else {
					result = -1;  // i1 is null and i2 is not (correct order)
				}
			} else if (i2.isNull()){
				result = 1;       // i1 is not null and i2 is (reverse order)
			} else {              // neither is null
				result = i1.lower().compareTo(i2.lower());
				if (result == 0){
					result = i1.upper().compareTo(i2.upper());
				}
			}
			return result;
		}
		
	};
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
	// this could be changed for a simple List<Interval> as long as it's kept
	// Collections.sort(List<Interval>, LOWER_UPPER)ed
	public SortedSet<Interval> intervals = new TreeSet<Interval>(LOWER_UPPER);
//------------------------------------------------------------------------------
	public IntervalSet(double lower, double upper,
			           boolean closed_lower, boolean closed_upper){
		intervals.add(new Interval(lower, upper, closed_lower, closed_upper));
	}
	
	public IntervalSet(double lower, double upper){
		intervals.add(new Interval(lower, upper));
	}
	
	public IntervalSet(double value){
		intervals.add(new Interval(value));
	}
	
	public IntervalSet(Interval i){
		if (!i.isNull()){
			intervals.add(i);
		}
	}

	protected IntervalSet(IntervalSet is){
		intervals.addAll(is.intervals);
	}

	private IntervalSet(Collection<Interval> intervals){
		// the argument intervals need to be mutually exclusive
		// if you were wanting to call this, consider unionAll()
	    intervals.remove(Interval.NULL);
	    assert(!intervals.contains(Interval.NULL));
		this.intervals.addAll(intervals);
	}
	
	private IntervalSet(){ // for use only in constructing a null interval set
	}
//------------------------------------------------------------------------------
	@Override
	public boolean equals(Object o){
		boolean result = false;
		if (o instanceof IntervalSet){
			IntervalSet is = (IntervalSet) o;
			result = equals(is);
		}
		return result;
	}
	
	@Override
	public int hashCode(){
		return intervals.hashCode();
	}
	
	@Override
	public String toString(){
		StringBuilder sb = new StringBuilder();
		if (isNull()){
			sb.append(Interval.NULL);
		} else {
			sb.append("{");
			Iterator<Interval> i_it = intervals.iterator();
			if (i_it.hasNext()){
				Interval i = i_it.next();
				sb.append(i);
				while(i_it.hasNext()){
					i = i_it.next();
					sb.append(", ");
					sb.append(i);
				}
			}
			sb.append("}");
		}
		return sb.toString();
	}
//------------------------------------------------------------------------------
	public Bound lowerBound(){
        assert(!isNull());
		return intervals.first().lower();
	}
	
	public Bound upperBound(){
	    assert(!isNull());
		return intervals.last().upper();
	}
	
	public Iterator<Interval> iterator() {
		return intervals.iterator();
	}
	
	public double getLength(){
		double result = 0.0;
		for(Interval i: intervals){
			result += i.getLength();
		}
		return result;
	}
	
	public int getIntervalCount(){
		return intervals.size();
	}

	public boolean isUnbounded(){
	    return ( (Double.isInfinite(lowerBound().value())) ||
	             (Double.isInfinite(lowerBound().value())) );
	}
	
	public boolean isBounded(){
	    return !isUnbounded();
	}
//------------------------------------------------------------------------------
	public boolean isNull(){
		return intervals.isEmpty();
	}
	
	public boolean equals(Interval i){
		return equals(new IntervalSet(i));
	}
	
	public boolean equals(IntervalSet is){
		return intervals.equals(is.intervals);
	}
	
	public Interval hull(){
		Interval result;
		if (isNull()){
            result = Interval.NULL;
		} else {
            result = new Interval(lowerBound(), upperBound());
		}
		return result;
	}
	
	public boolean subsetOf(Interval i){
		return hull().subsetOf(i);
	}
	
	public boolean subsetOf(IntervalSet is){
		// is is a superset of each interval in this 
		boolean result = true;
		if (!isNull()){
			Iterator<Interval> this_it = iterator();
			while(result && this_it.hasNext()){
				result = is.supersetOf(this_it.next());
			}
		}
		return result;		 
	}
	
	public boolean supersetOf(Interval i){
		boolean result = false;
		Iterator<Interval> i_it = iterator();
		while (!result && i_it.hasNext()){
			result = i_it.next().supersetOf(i);
		}
		return result;
	}
	
	public boolean supersetOf(IntervalSet is){
		return is.subsetOf(this);
	}
//------------------------------------------------------------------------------
	public IntervalSet complement(){
		Collection<Interval> result = new ArrayList<Interval>(intervals.size() + 1);
		if (isNull()){
			result.add(Interval.UNIVERSE);
		} else {
			Iterator<Interval> i_it = iterator();
			if (i_it.hasNext()){
				Interval next = i_it.next();
				if (!next.lower().equals(Bound.LOWEST)){
					result.add(new Interval(Bound.LOWEST, next.lower().inverse()));
				}
				Interval prev = next;
				while(i_it.hasNext()){
					next = i_it.next();
					result.add(new Interval(prev.upper().inverse(), next.lower().inverse()));
					prev = next;
				}
				if (!next.upper().equals(Bound.HIGHEST)){
					result.add(new Interval(next.upper().inverse(), Bound.HIGHEST));
				}
			}
		}
		return new IntervalSet(result);
	}
	
	public IntervalSet intersection(Interval i){
		Set<Interval> result = new HashSet<Interval>();
		for(Interval this_i: this){
			result.add(this_i.intersection(i));
		}
        // the constructor will remove Interval.NULL if it's present
		return new IntervalSet(result);
	}
	
	public IntervalSet intersection(IntervalSet is){
		Set<Interval> result = new HashSet<Interval>();
		for(Interval this_i: this){
			for(Interval is_i: is){
				result.add(this_i.intersection(is_i));
			}
		}
		// the constructor will remove Interval.NULL if it's present
		return new IntervalSet(result);
	}
	
	public IntervalSet union(Interval i){
		Collection<Interval> result = new ArrayList<Interval>(intervals.size() + 1);
		result.addAll(intervals);
		result.add(i);
		return unionAll(result);
	}
	
	public IntervalSet union(IntervalSet is){
		Collection<Interval> result =
				new ArrayList<Interval>(intervals.size() + is.intervals.size());
		result.addAll(intervals);
		result.addAll(is.intervals);
		return unionAll(result);
	}
	
	public IntervalSet setDifference(Interval i){
		return (intersection(new IntervalSet(i.complement())));
	}
	
	public IntervalSet setDifference(IntervalSet is){
		return intersection(is.complement());
	}
	
	public IntervalSet setSymmetricDifference(Interval i){
		return union(i).intersection(intersection(i).complement());
	}
	
	public IntervalSet setSymmetricDifference(IntervalSet is){
		return union(is).intersection(intersection(is).complement());
	}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
	public static IntervalSet unionAll(Collection<Interval> i_col){
		SortedSet<Interval> input = new TreeSet<Interval>(LOWER_UPPER);
		input.addAll(i_col);
		input.remove(Interval.NULL);
		SortedSet<Interval> result = new TreeSet<Interval>(LOWER_UPPER);
		if (input.size() > 0){
			Interval tmp = Interval.NULL;
			for(Interval i: input){
				List<Interval> tmp_union = tmp.union(i);
				if (tmp_union.size() == 1){ // they overlapped, keep unioning
					tmp = tmp_union.get(0);
				} else {         // they didn't overlap, save single and move on
					assert(tmp_union.size() == 2);
					result.add(tmp_union.get(0));
					tmp = tmp_union.get(1);
				}
			}
			result.add(tmp);
		}
        // the constructor will remove Interval.NULL if it's present
		return new IntervalSet(result);
	}
//------------------------------------------------------------------------------
}
